// ============================================================================================================================================================ Контрольная работа 1 Может ли матрица размером 3х3 иметь 7 седловых точек? Может ли матрица 4х4 иметь 11 седловых точек? имеет ли функция ??? на единичном квадрате ??? седловую точку? Если да, то найти все седловые точки. Найти решение в смешанных стратегиях в игре с платежной матрицей ??? Найти все оптимальные стратегии первого игрока в игре с платежной матрицей ??? Найти все ситуации равновесия в биматричной игре: ??? ??? // ============================================================================================================================================================ Контрольная работа 2 Билет 4 1. Дана сеть G с дугами (1, 2), (1, 3), (1,4), (1, 5), (2, 5), (2,6), (2, 8), (3, 2), (3, 6), (4, 3), (4, 6), (4, 7), (5, 8), (6, 8), (7, 8), пропускные способности которых равны соответственно 3, 3, 4, 3, 2, 2, 4, 2, 3, 3, 3, 3, 4, 4, 4. А. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Форда-Фалкерсона. В качестве начального взять нулевой поток. Для каждой итерации указать увеличивающий путь и величину увеличения потока. B. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Карзанова. В качестве начального взять нулевой поток. Для каждого этапа указать сеть G(f), слоистую сеть G*(f) и тупиковый поток в ней. C. Построить минимальный разрез в сети G. 2. Дана сеть G с дугами (0, 1), (0,2), (1,2), (2, 1), (1, 3), (2, 3), (3, 0), параметры которых равны соответственно (1, 8, 1), (1, 8, 1), (2, 3, 1), (0, 3, 0), (1, 6, 2), (1,4, 1), (3, 5, 1) (дуга (i,j) имеет параметры Lij, Uij, cij, где Lij - нижняя граница потока по дуге, Uij - верхняя граница потока по дуге, с,, - стоимость единицы потока по дуге). С помощью алгоритма дефекта найти циркуляцию минимальной стоимости в сети G. В качестве начального взять нулевой поток. Для каждой итерации указать поток по каждой дуге, наличие или отсутствие ее дефекта, возможные изменения потока по ней, узловые числа. При изменении потоков указать соответствующий цикл и величину изменения потока, а при изменении узловых чисел привести соответствующие вычисления. 3. Даны вычислительная система, состоящая из двух идентичных процессоров, и четыре работы со следующими характеристиками: Работа I bi fi ti 1 0 5 4 2 1 6 4 3 0 8 2 4 0 8 6 (bi, fi, ti - соответственно начальный директивный срок, конечный директивный срок и длительность выполнения работы i). Определить, существует ли допустимое расписание с прерываниями и найти его, если оно существует. Издержками на прерывания и переключения пренебречь. Свести указанную задачу к задаче о максимальном потоке в сети. При нахождении максимального потока привести все вычисления. // ============================================================================================================================================================ Контрольная работа 2 Билет 3 1. Дана сеть G с дугами (1, 2), (1, 3), (1,4), (2, 5), (2, 7), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (4, 7), (4, 8), (5, 8), (6, 8), (7, 6), (7, 8), пропускные способности которых равны соответственно 6, 6, 6, 3, 3, 3, 2, 3, 1, 3, 4, 6, 4, 6, 1, 4. A. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Форда-Фалкерсона. В качестве начального взять нулевой поток. Для каждой итерации указать увеличивающий путь и величину увеличения потока. B. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Карзанова. В качестве начального взять нулевой поток. Для каждого этапа указать сеть G(f), слоистую сеть G*(f) и тупиковый поток в ней. C. Построить минимальный разрез в сети G. 2. Дана сеть G с дугами (0, 1), (0,2), (1,2), (2, 1), (1, 3), (2, 3), (3, 0), параметры которых равны соответственно (0, 5, 2), (2, 5, 2), (1, 1, 0), (1, 2, 0), (2, 6, 2), (3, 6, 1), (7, 9, 0) (дуга (i,j) имеет параметры Lij, Uij, cij, где Lij - нижняя граница потока по дуге, Uij - верхняя граница потока по дуге, с,, - стоимость единицы потока по дуге). С помощью алгоритма дефекта найти циркуляцию минимальной стоимости в сети G. В качестве начального взять нулевой поток. Для каждой итерации указать поток по каждой дуге, наличие или отсутствие ее дефекта, возможные изменения потока по ней, узловые числа. При изменении потоков указать соответствующий цикл и величину изменения потока, а при изменении узловых чисел привести соответствующие вычисления. Даны вычислительная система, состоящая из двух идентичных процессоров, и четыре работы со следующими характеристиками: Работа I bi fi ti 1 1 6 3 2 1 5 3 3 0 6 3 4 0 4 3 (bi, fi, ti - соответственно начальный директивный срок, конечный директивный срок и длительность выполнения работы i). Определить, существует ли допустимое расписание с прерываниями и найти его, если оно существует. Издержками на прерывания и переключения пренебречь. Свести указанную задачу к задаче о максимальном потоке в сети. При нахождении максимального потока привести все вычисления. // ============================================================================================================================================================ Контрольная работа 2 Билет 2 1. Дана сеть G с дугами (1, 2), (I, 3), (1,4), (2, 3), (2, 5), (2,6), (2, 8), (3, 6), (3, 7), (4, 6), (4, 7), (5, 8), (6, 5), (6, 8), (7, 8), пропускные способности которых равны соответственно 3, 4, 5, 1,3, 1, 2, 2, 3, 4, 2, 5, 2, 4, 2. A. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Форда-Фалкерсона. В качестве начального взять нулевой поток. Для каждой итерации указать увеличивающий путь и величину увеличения потока. B. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Карзанова. В качестве начального взять нулевой поток. Для каждого этапа указать сеть G(f), слоистую сеть G*(f) и тупиковый поток в ней. C. Построить минимальный разрез в сети G. 2. Дана сеть G с дугами (0, 1), (0,2), (1,2), (2, 1), (1, 3), (2, 3), (3, 0), параметры которых равны соответственно (0, 6, 1), (0, 8, 2), (1, 3, 1), (1, 3, 1), (2, 6, 3), (2, 5, 4), (4, 5, 1) (дуга (i,j) имеет параметры Lij, Uij, cij, где Lij - нижняя граница потока по дуге, Uij - верхняя граница потока по дуге, с,, - стоимость единицы потока по дуге). С помощью алгоритма дефекта найти циркуляцию минимальной стоимости в сети G. В качестве начального взять нулевой поток. Для каждой итерации указать поток по каждой дуге, наличие или отсутствие ее дефекта, возможные изменения потока по ней, узловые числа. При изменении потоков указать соответствующий цикл и величину изменения потока, а при изменении узловых чисел привести соответствующие вычисления. 3. Даны вычислительная система, состоящая из двух идентичных процессоров, и четыре работы со следующими характеристиками: Работа I bi fi ti 1 0 1 5 2 1 4 2 3 0 7 5 4 2 5 2 (bi, fi, ti - соответственно начальный директивный срок, конечный директивный срок и длительность выполнения работы i). Определить, существует ли допустимое расписание с прерываниями и найти его, если оно существует. Издержками на прерывания и переключения пренебречь. Свести указанную задачу к задаче о максимальном потоке в сети. При нахождении максимального потока привести все вычисления. // ============================================================================================================================================================ Контрольная работа 2 Билет 1 1. Дана сеть G с дугами (1, 2), (1, 3), (1,4), (2, 3), (2, 5), (2,6), (3, 5), (3, 6), (3, 7), (4, 3), (4, 5), (4, 7), (5, 8), (6, 8), (7, 8), пропускные способности которых равны соответственно 2, 4, 6, 1, 1, 1, 2, 2, 2, 1, 3, 3, 5, 3, 4. A. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Форда-Фалкерсона. В качестве начального взять нулевой поток. Для каждой итерации указать увеличивающий путь и величину увеличения потока. B. Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Карзанова. В качестве начального взять нулевой поток. Для каждого этапа указать сеть G(f), слоистую сеть G*(f) и тупиковый поток в ней. C. Построить минимальный разрез в сети G. 2. Дана сеть G с дугами (0, 1), (0,2), (1,2), (2, 1), (1, 3), (2, 3), (3, 0), параметры которых равны соответственно (2, 4, 2), (2, 4, 5), (0, 1, 1), (0, 1, 1), (3, 4, 3), (1, 2, 6), (3, 4, 0) (дуга (i,j) имеет параметры Lij, Uij, cij, где Lij - нижняя граница потока по дуге, Uij - верхняя граница потока по дуге, с,, - стоимость единицы потока по дуге). С помощью алгоритма дефекта найти циркуляцию минимальной стоимости в сети G. В качестве начального взять нулевой поток. Для каждой итерации указать поток по каждой дуге, наличие или отсутствие ее дефекта, возможные изменения потока по ней, узловые числа. При изменении потоков указать соответствующий цикл и величину изменения потока, а при изменении узловых чисел привести соответствующие вычисления. 3. Даны вычислительная система, состоящая из двух идентичных процессоров, и четыре работы со следующими характеристиками: Работа I bi fi ti 1 0 4 3 2 2 5 2 3 1 6 2 4 0 6 5 (bi, fi, ti - соответственно начальный директивный срок, конечный директивный срок и длительность выполнения работы i). Определить, существует ли допустимое расписание с прерываниями и найти его, если оно существует. Издержками на прерывания и переключения пренебречь. Свести указанную задачу к задаче о максимальном потоке в сети. При нахождении максимального потока привести все вычисления. // ============================================================================================================================================================ Контрольная работа 3 Вариант 1 1. Верно ли, что класс языков Р замкнут относительно операции объединения? 2. Является ли NP-полной задача «Целочисленное линейное программирование»? (Заданы матрица А с элементами аij (i=1,..., т; j=l,...,n), векторы c=(c1,...,cn), b=(b1,...,bm) и число Т. Существует ли целочисленный неотрицательный вектор х=(х1,...,хn), такой, что (с,х) >= Т, Ах <= b ?). Является ли эта задача co-NP-полной? При доказательстве NP-полноты можно пользоваться NP-полнотой только семи основных NP-полных задач. 3. Является ли NP-полной в сильном смысле задача «Расписание для многопроцессорной системы»? (Заданы множество работ N={I,...,n}, число идентичных процессоров m, длительности ti, выполнения работ и общий директивный интервал [0, Т] для всех работ. Существует ли допустимое m-процессорное расписание выполнения работ из N без прерываний и переключений, такое, что ti + ti <Т при всех iI принадлежит N. где ti - момент начала выполнения работы i ?). 4. Доказать, что оптимизационная задача «Упаковка в контейнеры» (Заданы множество предметов N={I,...,n}, их объемы vi и объем V контейнеров. Требуется упаковать все предметы из N в минимальное число контейнеров) является NP-трудной и NP-легкой. 5. Существует ли приближенный полиномиальный алгоритм А решения задачи 4 с оценкой rA2<=K,где К - константа? // ============================================================================================================================================================ Контрольная работа 3 Вариант 2 1. Верно ли, что класс языков Р замкнут относительно операции пересечения? 2. Является ли NP-полной задача «Трехпроцессорное расписание»? (Заданы множество работ N={1,...,п}, три идентичных процессора, длительности ti выполнения работ и общий для всех работ директивный интервал [0, Т]. Существует ли допустимое трехпроцессорное расписание выполнения работ из N без прерываний и переключений, такое, что ti + ti <=Т при всех iI принадлежащих N, где ti - момент начала выполнения работы i?). Является ли эта задача co-NP-полной? При доказательстве NP-полноты можно пользоваться NP-полнотой только семи основных NP-полных задач. 3. Является ли NP-полной в сильном смысле задача «Упаковка в контейнеры»? (Заданы множество предметов N={1,...,n}, их объемы vi, объем V контейнеров и число К. Можно ли упаковать все предметы из N в К контейнеров?). 4. Доказать, что оптимизационная задача «Многопроцессорное расписание» (Заданы множество работ N={1,...,n}, число идентичных процессоров m и длительности ti, выполнения работ. Найти оптимальное по быстродействию расписание выполнения работ N без прерываний и переключений) является NP-трудной и NP-легкой. 5. Существует ли приближенный полиномиальный алгоритм А решения задачи 4 с оценкой rA2<=К, где К - константа? // ============================================================================================================================================================ Контрольная работа 3 Вариант 3 1. Верно ли, что класс языков NP замкнут относительно операции объединения? 2. Является ли NP-полной задача «Минимизация штрафа за невыполнение работ на одном процессоре»? (Даны множество работ N={1,...,n}, длительность ti, вес wi и директивный интервал (bi,fi] для каждой работы iI принадлежит N и число К. Существует ли однопроцессорное расписание t=(t1,..., tn) без прерываний и переключений (ti - момент начала выполнения работы i), такое, что ?). Является ли эта задача со-NP-полной? При доказательстве NP-полноты можно пользоваться NP-полнотой только семи основных NP-полных задач. 3. Является ли NP-полной в сильном смысле задача 2? 4. Доказать, что оптимизационная задача «Рюкзак» (Заданы набор предметов N={1,...,n}, их объемы vi и стоимости si и объем рюкзака V. Найти подмножество предметов из N, имеющих максимальную суммарную стоимость и вмещающихся в рюкзак) является NP-трудной и NP-легкой. 5. Существует ли приближенный полиномиальный алгоритм А решения оптимизационной задачи «Независимое множество» (Дан граф G = (V, А). Найти независимое множество максимальной мощности) с оценкой rA2 <=K, где К - константа? // ============================================================================================================================================================ Контрольная работа 3 Вариант 4 1. Верно ли, что класс языков NP замкнут относительно операции пересечения? 2. Является ли NP-полной задача «Минимизация штрафа за невыполнение работ на т процессорах»? (Даны множество работ N={1,...,n}, длительность ti вес wi для каждой работы iI принадлежит N, общий директивный интервал [0, T] для всех работ, число m идентичных процессоров и число К. Существует ли т - процессорное расписание без прерываний и переключений, такое, что ( ti - момент начала выполнения работы i) ?). Является ли эта задача co-NP-полной? При доказательстве NP-полноты можно пользоваться NP-полнотой только семи основных NP-полных задач. 3. Является ли NP-полной в сильном смысле задача 2? 4. Доказать, что оптимизационная задача «Клика» (Задан граф G = (V, А). Найти клику максимальной мощности) является NP-трудной и NP-легкой. 5. Существует ли приближенный полиномиальный алгоритм А решения задачи 4 с оценкой rA1 <=К где К- константа?